package com.hy.node;

public class ReserveNode {

    /**
     * 206.反转链表
     *
     * 题意：反转一个单链表。
     *
     * 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
     * 思路
     * 如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
     *
     * 其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
     * 1    ->  2   ->  3   ->  4   ->  5   ->  null
     * null  <- 1   <-  2   <-  3   <-  4   <-  5
     * 之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向
     *
     * 思路：
     * 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
     *
     * 然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
     *
     * 为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
     *
     * 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
     *
     * 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
     */

    static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 双指针法
     *
     * 两两节点 交换位置。
     * @param head
     * @return
     */
    public static ListNode reserveElements(ListNode head){
        ListNode cur = head;
        ListNode pre = null;
        ListNode temp = null;
        while (cur!= null){
            // 首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
            temp = cur.next;
            // 反转操作  1 -> null  2 -> 1
            cur.next = pre;
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 递归法
     * 递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
     *
     * 关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，
     * 在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。

     * @return
     */
    public static ListNode reverseElements2(ListNode head) {
        // 边缘条件判断
        if (head == null || head.next == null){
            return head;
        }
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseElements2(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    }




    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5,null);
        ListNode listNode4 = new ListNode(4,listNode5);
        ListNode listNode3 = new ListNode(3,listNode4);
        ListNode listNode2 = new ListNode(2,listNode3);
        ListNode listNode1 = new ListNode(1,listNode2);

        System.out.println("反转元素前："+listNode1);

        System.out.println("反转元素后："+reserveElements(listNode1));

        System.out.println("反转元素后2 ："+reverseElements2(listNode5));


    }
}
